In the field of computing hardware, there is a class of global optimization problems which is typified by the so-called "traveling salesman problem" (TSP). In the TSP, a salesman with N cities on his itinerary is to select the round-trip tour that goes through each of the N cities and minimizes the total distance travelled. As those skilled in the art are well aware, such "global optimization problems" are very computation intensive since the time required to find the optimal tour solution by an exhaustive search grows faster than any polynomial function as the size of the problem increases.
In the past, a variety of heuristic search algorithms have been applied to this problem with varying degrees of efficiency. Artificial neural network approaches to TSP have also been proposed in recent years (e.g. Hopfield and Tank in 1985). These prior art neural network approaches to TSP typically require a large number 2N.sup.3 for N cities of analog synapses. Such prior art neural network solutions have been tested on software digital simulators; however, their hardware implementation as an actual neural network have seldom been attempted due primarily to the involved hardware complexity in the artwork architectures.
Multiparameter optimization problems impose multiple constraints, to be dealt with simultaneously, to select the "best situation" or the global solution under given conditions. With increasing dimensionality, therefore, solutions of such problems become highly computation intensive. A brute force approach in a complex situation requires actual comparison and search through all possible solutions to determine and select the "lowest cost" situation. In the case of the TSP, for example, for the N cities the possible number of distinct tours is given by T=(N)!/2N. For four cities, the number of tours is only three. For only eight cities, however, the number grows to 2,520. At only twelve cities, the number of tours leaps to almost 20 million. Clearly, such problems quickly approach a level where a brute force approach is impractical even at modern computer speeds. In portable implementations, for example, where computer power is very limited, a better solution is obviously needed.
The above-mentioned neural network solution of the TSP proposed by Hopfield and Tank consists of an NxN array of neurons. The rows are labelled by the cities and the columns by the order in which the cities are visited. Thus, a valid tour corresponds to having only a single active neuron in each row as well as in each column of the neuron array. Lateral inhibition along the rows as well as columns is required to enforce these constraints, in addition to a large number (.sup..about. 2N.sup.3) of analog synapses to "store" the inter-city distance information. Although the algorithm does capture all the constraints in the proposed network, the complexity of the network architecture has been the primary constraint in preventing its actual hardware implementation. In other words, it works in simulation; but, is too complex to build in actuality. The promise of high speed solutions to TSP and similar global optimization problems from the neural net approach, therefore, has not been realized so far.